//package advancedJava;

import java.io.*;
import java.util.*;
import java.text.*;
import java.awt.geom.*;

/**
 * Title: DiGraph
 *
 * @author Ian Foley
 * @version 1.1 - Copyright(c) October 2012, prev April, 2002 
 *
 * Extensively modified from the code by Mark Allen Weiss.  (2012 changed 
 * HashMap vertexMapNo to ArrayList<Vertex>.  Rob Allen)
 *
 * Description
 *  Classes to create a digraph and determine and evaluate shortest paths
 *  using Dijkstra's algorithm.
 *
 * Process that needs to be followed to create a DiGraph.
 *
 * 1. Create a DiGraph object, e.g.
 *      DiGraph dg = new DiGraph();
 * 2. Iterate through all the edges in the graph performing steps 3 and 4 in each
 *    iteration. When completed, go to step 5.
 * 3. Assume the data for each edge is of the form
 *    x1|y1|x2|y2
 *     where x1,y1 and x2,y2 are the coordinates at the beginning and ending of an edge
 *    Call the getVertex() method first for the vertices at the beginning and ending
 *    of the edge to see if the vertex has already been created.
 *    If it does not exist call createVertex() to create a new Vertex.
 *    e.g
 *     Point2D p1;
 *     Point2D p2;
 *     p1 = new Point2D.Double(x1,y1);
 *     p2 = new Point2D.Double(x2,y2);
 *     Vertex v1 = dg.getVertex(p1);
 *     if (v1 == null)
 *      v1 = dg.createVertex(p1);
 *     Vertex v2 = dg.getVertex(p2);
 *     if (v2 == null)
 *      v2 = dg.createVertex(p2);
 * 4. After retrieving or creating each vertex, create the edges between the vertices.
 *    Note that we are creating a directional graph.
 *    So create 1 edge from p1 -> p2 or p2 -> p1 if there is one edge or
 *    Create 2 edges if both directions are valid.
 *    e.g
 *     dg.addEdge(v1,v2,p1.distance(p2));
 *     dg.addEdge(v2,v1,p2.distance(p1));
 *    for a bidirectional edge. In this example, the cost is the distance between the
 *    two points.
 * 5. Call dg.getVertexNo()+1 and dg.getEdgeNo()+1 to see the total number of verticies
 *    and total number of edges. The directional graph has been created.
 *
 * Process that needs to be followed to find the shortest path between two points p1 and p2
 *
 * 1. Select the starting point p1. This could be done through a mouse click
 *    It is assumed that p1 is a Point2D object created in user coordinates NOT device
 *    coordinates. Then call the dijkstra method to create all the shortest paths from
 *    the Vertex v1 found from p1.
 *    e.g.
 *     dg.dijkstra(p1,radius);
 *    where radius defines the size of a rectangle around p1 within which the search for a vertex
 *    will be made.
 *    If you know the vertex number you can call dg.dijkstra(vertexNo) instead.
 * 2. Select the ending point p2. This could be done in the same way as the starting point.
 *    The call the getPath() method to retrieve the shortest path from p1 to p2.
 *    e.g
 *     Vertex v2 = dg.getPath(p2,radius,"units");
 *    The console will display the distance from v1 to v2 along the shortest path.
 * 3. Display the path in a console window.
 *    e.g
 *     dg.printPath(v2);
 *    printPath() is a recursive routine and traces the path back from the end point to
 *    the starting point. Because it's recursive the nodes are displayed from starting
 *    point to the ending point.
 *    Since we may prefer to trace the shortest path from the starting point to the ending
 *    point a LinkedList object called shortestPath is used to store the vertices from
 *    the starting point to the ending point.
 *    This object is instantiated when the DiGraph object is created or  a new path
 *    generated. You must call dg.printPath() to add the vertices to this
 *    object.
 * 4. To display the shortest path, successively call v.getPrevious() until it equals null
 *    to get the shortest path starting with the ending vertex v2.
 *    OR
 *    Iterate through the LinkedList object obtained by calling dg.getShortestPath()
 */

public class DiGraph
{
    public static final double INFINITY = Double.MAX_VALUE;
    private List<Vertex> vertexList = new ArrayList<Vertex>();  // Maps vertex number
    private HashMap<String,Vertex> vertexMapXY = new HashMap<String,Vertex>();  // Maps x|y coordinate as a string
    private int vertexNo = -1;
    private int edgeNo = -1;
    private LinkedList<Vertex> shortestPath = null;
    
    /**
     *  Constructor
     */
    public DiGraph()
    {
        shortestPath = new LinkedList<Vertex>();
    }
    
    /**
     *  Retrieve the last vertex number.
     *  @return the last vertex number
     */
    public int getVertexNo()
    {
        return vertexNo;
    }
    
    /**
     *  Retrieve the last edge number.
     *  @return the last edge number
     */
    public int getEdgeNo()
    {
        return edgeNo;
    }
    
    /**
     *  Add a new edge from vertex v to vertex w with cost c to the graph.
     */
    public void addEdge(Vertex v, Vertex w, double c)
    {
        edgeNo++;
        (v.getAdjacent()).add(new Edge(edgeNo,w,c));
    }
    
    /**
     *  Find vertex nearest to point p which is at the end point of the shortest path
     *  p could have been determined from a mouse click, keyboard entry
     *  or a data file entry and therefore may not exactly correspond
     *  to the stored value of the point. radius is used to calculate
     *  a rectangle surrounding p. The first Vertex found within this
     *  rectangle is assumed to be the one desired.
     *  unit is the distance measure.
     *  @return the ending vertex or null if vertex is not found or
     *  the vertex is unreachable.
     */
    public Vertex getPath(Point2D p,int radius,String unit)
    {
        String pt = null;
        
        pt = (long)p.getX()+"|"+(long)p.getY();
        Vertex w = vertexMapXY.get(pt);
        if (w == null)
        {
            boolean found = false;
            Point2D testPoint = null;
            
            /*
               Get nearest vertex by creating a small rectangle around p
               and then scanning all vertices to find the first one whose
               location is within the rectangle.
             */
            Rectangle2D r = new Rectangle2D.Double(p.getX()-radius,p.getY()-radius,2*radius,2*radius);
            for (int i = 0; i < vertexNo; i++)
            {
                w = vertexList.get(i);
                if (w != null)
                {
                    testPoint = w.getPoint2D();
                    if (r.contains(testPoint))
                    {
                        found = true;
                        break;
                    }
                }
            }
            if (found)
            {
                pt = (long)testPoint.getX()+"|"+(long)testPoint.getY();
            }
            else
            {
                System.out.println("Getting Path: Point not found");
                w = null;
            }
        }
        
        if (w == null)
            System.out.println("Getting Path: Destination vertex not found");
        else
            if(w.getDistance() == INFINITY)
            {
                System.out.println("First "+pt + " is unreachable");
                w = null;
            }
            else
            {
                DecimalFormat df = new DecimalFormat("##0");
                System.out.println("Distance: " + df.format(w.getDistance())+" "+unit);
            }
        return w;
    }
    /**
	 * New Method added by L.Matthews (student HIT8087, 2002) to obtain the nearest
     * vertex around a Point 2D.
     *
     * Code taken from getPath();
     * also have replaced missing code from getPath() with a method call to this method
     * @return nearest vertex to p, or null if not found within square of side 2*radius
     * centred on p.
     */
    public Vertex getNearest(Point2D p, int radius)
    {
        String pt = null;
        pt = (long)p.getX()+"|"+(long)p.getY();
        Vertex w = vertexMapXY.get(pt);
        Point2D testPoint = null;
        boolean found = false;
        /**
         *  Get nearest vertex by creating a small rectangle around p
         *  and then scanning all vertices to find the first one whose
         *  location is within the rectangle.
         */
        Rectangle2D r = new Rectangle2D.Double(p.getX()-radius,p.getY()-radius,2*radius,2*radius);
        for (int i = 0; i < vertexNo; i++)
        {
            w = vertexList.get(i);
            if (w != null)
            {
                testPoint = w.getPoint2D();
                if (r.contains(testPoint))
                {
                    found = true;
                    break;
                }
            }
        }
        return w;        
    }
    
    /**
     * Display shortest path to vertex w
     * after running shortest path algorithm.
     */
    public void printPath(Vertex w)
    {
        if (w == null)
        {
            System.out.println("No vertex, path cannot be followed");
            return;
        }
        if (w.getPrevious() != null)
        {
            printPath(w.getPrevious());
        }
        System.out.println("Vertex "+w.getNumber()+" - "+(w.getPoint2D()).getX()+","+
        (w.getPoint2D()).getY());
        shortestPath.add(w);
    }
    
    public List<Vertex> getShortestPath()
    {
        return shortestPath;
    }
    
    /**
     *  Find a vertex at point p.
     *  @returns null if not found.
     */
    public Vertex getVertex(Point2D p)
    {
        String pt = null;
        
        pt = (int)p.getX()+"|"+(int)p.getY();
        Vertex v = vertexMapXY.get(pt);
        return v;
    }
    
    /**
     *  Find a vertex given the vertex number.
     *  @returns null if not found.
     */
    public Vertex getVertex(int vertexNo)
    {
        Vertex v = vertexList.get(vertexNo);
        return v;
    }
    
    /**
     *  Create a vertex at point p
     *  @returns the vertex
     */
    public Vertex createVertex(Point2D p)
    {
        String pt = null;
        
        pt = (long)p.getX()+"|"+(long)p.getY();
        vertexNo++;
        Vertex v = new Vertex(vertexNo, p);
        vertexList.add(vertexNo, v);
        vertexMapXY.put(pt,v);
        return v;
    }
    
    /**
     *  Resets all the vertices links and values prior to executing
     *  any shortest path algorithm.
     */
    private void clearAll()
    {
        shortestPath = new LinkedList<Vertex>();
        for (Iterator<Vertex> itr = vertexList.iterator(); itr.hasNext();)
            itr.next().reset();
    }
    
    /**
     *  Dijkstra's single-source weighted shortest path algorithm.
     *  Starts with a given point which may not be exactly right,
     *  although it should be close. The first vertex within a rectangle
     *  of the point is assumed to be the starting Vertex.
     */
    public void dijkstra(Point2D p, int radius)
    {
        String pt = null;
        Point2D testPoint = null;
        int startNo;
        
        pt = (long)p.getX()+"|"+(long)p.getY();
        Vertex v = vertexMapXY.get(pt);
        if (v == null)
        {
            boolean found = false;
            
            /**
             *  Get nearest vertex by creating a small rectangle around p
             *  and then scanning all vertices to find the first one whose
             *  location is within the rectangle.
             */
            Rectangle2D r = new Rectangle2D.Double(p.getX()-radius,p.getY()-radius,2*radius,2*radius);
            for (int i = 0; i < vertexNo; i++)
            {
                v = vertexList.get(i);
                if (v != null)
                {
                    testPoint = v.getPoint2D();
                    if (r.contains(testPoint))
                    {
                        found = true;
                        break;
                    }
                }
            }
            if (found)
            {
                pt = (long)testPoint.getX()+"|"+(long)testPoint.getY();
                System.out.println("Nearest point ("+pt+") found, path being generated");
                startNo = v.getNumber();
                dijkstra(startNo);
            }
            else
                System.out.println("Dijkstra's Algorithm: Point not found");
        }
        else
        {
            System.out.println("Point ("+pt+") found, path being generated");
            startNo = v.getNumber();
            dijkstra(startNo);
        }
    }
    
    
    /**
     *  Dijkstra's Single-source weighted shortest path algorithm.
     *  Starts with a given vertex number
     */
    public void dijkstra(int startNo)
    {
        PQ pq = new PQ();
        
        Vertex start = vertexList.get(startNo);
        if (start == null)
            throw new NoSuchElementException("Start vertex not found");
        
        clearAll();
        pq.insert(new Path(start,0));
        start.setDistance(0);
        
        int nodesSeen = 0;
        while (!pq.isEmpty() && nodesSeen < vertexList.size())
        {
            Path vrec = (Path)pq.deleteMin();
            Vertex v = vrec.getDestination();
            if(v.getScratch() != 0)  // already processed v
                continue;
            
            v.setScratch(1);
            nodesSeen++;
            
            for(Iterator<Edge> itr = (v.getAdjacent()).iterator(); itr.hasNext();)
            {
                Edge e = itr.next();
                Vertex w = e.getDestination();
                double cvw = e.getCost();
                
                if (w.getDistance() > v.getDistance() + cvw)
                {
                    w.setDistance(v.getDistance() +cvw);
                    w.setPrevious(v);
                    pq.insert(new Path(w, w.getDistance()));
                }
            }
        }
    }
}

/**
 *  Class to represent a vertex in the graph
 *
 */
class Vertex
{
    private int        number;    // Vertex number
    private Point2D    p;         // Coordinates of vertex
    private List<Edge> adjacent;  // Adjacent vertices
    private double     distance;  // Cost
    private Vertex     previous;  // Previous vertex on shortest path
    private int        scratch;   // Extra variable used in algorithm
    
    public Vertex(int number, Point2D p)
    {
        this.number = number;
        this.p = p;
        adjacent = new LinkedList<Edge>();
        reset();
    }
    
    public void reset()
    {
        distance = DiGraph.INFINITY;
        previous = null;
        scratch = 0;
    }
    
    public int getNumber()
    {
        return number;
    }
    
    public Point2D getPoint2D()
    {
        return p;
    }
    
    public Vertex getPrevious()
    {
        return previous;
    }
    
    public void setPrevious(Vertex previous)
    {
        this.previous = previous;
    }
    
    public double getDistance()
    {
        return distance;
    }
    
    public void setDistance(double distance)
    {
        this.distance = distance;
    }
    
    public List<Edge> getAdjacent()
    {
        return adjacent;
    }
    
    public int getScratch()
    {
        return scratch;
    }
    
    public void setScratch(int scratch)
    {
        this.scratch = scratch;
    }
}

/**
 *  Class to represent an edge in the graph
 *
 */
class Edge
{
    private int edgeNo;
    private Vertex   destination;   // Second vertex in Edge
    private double     cost;        // Edge cost
    
    /**
	 *  Constructor
	 * @param edgeNo reference number (position in list of all vertexes)
	 * @param destination vertex at far end of this edge
	 * @param cost or distance along this edge
	 */
	public Edge(int edgeNo, Vertex destination, double cost)
    {
        this.edgeNo = edgeNo;
        this.destination = destination;
        this.cost = cost;
    }
    
    public int getEdgeNo()
    {
        return edgeNo;
    }
    
    public Vertex getDestination()
    {
        return destination;
    }
    
    public double getCost()
    {
        return cost;
    }
}

/**
 *  Class to represent an entry in the priority queue for Dijkstra's Algorithm
 *
 */
class Path implements Comparable<Path>
{
    private Vertex   destination;   // w
    private double     cost;   // d(w)
    
    public Path(Vertex destination, double cost)
    {
        this.destination = destination;
        this.cost = cost;
    }
    
    public Vertex getDestination()
    {
        return destination;
    }
    
    public int compareTo(Path rhs)
    {
        double otherCost = rhs.cost;
        
        return cost < otherCost ? -1 : cost > otherCost ? 1 : 0;
    }
}

/**
 *
 *  A Priority Queue
 *
 * An implementation of the PriorityQueue<Path> using the Binary Heap
 * All matching is based on the compareTo method.
 */
class PQ
{
    private int initialCapacity = 100;
    private int currentSize;      // Number of elements in heap
    private Path[] array;         // The heap array
    
    
    /**
     * Construct the priority queue with the default initial capacity.
     */
    public PQ( )
    {
        currentSize = 0;
        array = new Path[initialCapacity+1];
    }
    
    /**
     * Construct the priority queue with a given initial capacity.
     */
    public PQ(int initialCapacity)
    {
        this.initialCapacity = initialCapacity;
        currentSize = 0;
        array = new Path[initialCapacity+1];
    }
    
    /**
     * Construct the priority queue from an array.
     * @param items initial objects to place on the binary heap.
     */
    public PQ(Path[] items)
    {
        currentSize = items.length;
        array = new Path[items.length+1];
        
        for (int i = 0;i < items.length;i++)
            array[i+1] = items[i];
        buildHeap();
    }
    
    /**
     * Insert into the priority queue, maintaining heap order.
     * Duplicates are allowed.
     * @param x the item to insert.
     */
    public void insert(Path x)
    {
        if (currentSize+1 == array.length)
            doubleArray();
        
        // Percolate up
        int hole = ++currentSize;
        array[0] = x;
        
        for ( ; x.compareTo(array[hole/2]) < 0; hole /= 2)
            array[hole] = array[hole/2];
        array[hole] = x;
    }
    
    /**
     * Find the smallest item in the priority queue.
     * @return the smallest item or null if empty.
     */
    public Comparable<Path> findMin()
    {
        if (isEmpty())
            return null;
        return array[1];
    }
    
    /**
     * Remove the smallest item from the priority queue.
     * @return the smallest item or null if empty.
     */
    public Comparable<Path> deleteMin()
    {
        Comparable<Path> minItem = findMin();
        if (minItem == null)
            return null;
        array[1] = array[currentSize--];
        percolateDown(1);
        
        return minItem;
    }
    
    /**
     * Test if the priority queue is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty()
    {
        return currentSize == 0;
    }
    
    /**
     * Make the priority queue logically empty.
     */
    private void makeEmpty()
    {
        currentSize = 0;
    }
    
    /**
     * Returns the size.
     * @return current size.
     */
    private int size()
    {
        return currentSize;
    }
    
    /**
     * Establish heap order property from an arbitrary
     * arrangement of items. Runs in linear time.
     */
    private void buildHeap()
    {
        for (int i = currentSize/2; i > 0; i--)
            percolateDown(i);
    }
    
    /**
     * Internal method to percolate down in the heap.
     * @param hole the index at which the percolate begins.
     */
    private void percolateDown(int hole)
    {
        int child;
        Path tmp = array[hole];
        
        for ( ;hole * 2 <= currentSize; hole = child )
        {
            child = hole * 2;
            if (child != currentSize &&
            array[child+1].compareTo(array[child]) < 0 )
                child++;
            if (array[child].compareTo(tmp) < 0)
                array[hole] = array[child];
            else
                break;
        }
        array[hole] = tmp;
    }
    
    /**
     *  Dynamically doubles the queue capacity when it becomes full
     */
    private void doubleArray()
    {
        Path[] newArray;
        
        newArray = new Path[array.length * 2];
        for (int i = 0;i < array.length;i++)
            newArray[i] = array[i];
        array = newArray;
    }
    
}